class Solution:
    def numWays(self, n: int) -> int:
        if n <2 : return 1
        res = [1,1]
        for i in range(n-1):
            res.append(res[-1]+res[-2])
        return res[-1]
print(Solution().numWays(7))

class Solution:
    def numWays(self, n: int) -> int:
        if n <2 : return 1
        res = [1,1]
        for i in range(n-1):
            res.append((res[-1]+res[-2])%1000000007)
        return res[-1]